package com.github.yangyishe.p100;

import com.github.yangyishe.ListNode;

/**
 * 86. 分隔链表
 * https://leetcode.cn/problems/partition-list/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 示例 2：
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 */
public class Problem86 {
    public static void main(String[] args) {
        int[] arr=new int[]{1};
        ListNode head = ListNode.getInstance(arr);
        int x=2;

        Problem86 problem86 = new Problem86();
        ListNode partition = problem86.partition(head, x);
        partition.print();

    }

    /**
     * 思路:
     * 1. 创建两条新的链表, 一条记录小于x的节点链表, 一条记录大于等于x的节点链表
     * 两条链表的顺序均与原始顺序一致
     *
     * 最后将两条链表合并即可
     *
     * 注: 需要保证最后一个节点的next为空
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        if(head==null){
            return head;
        }
        ListNode leftHead=null;
        ListNode leftTail=null;
        ListNode rightHead=null;
        ListNode rightTail=null;

        ListNode temp=head;
        while(temp!=null){
            if(temp.val<x){
                if(leftHead==null){
                    leftHead=temp;
                    leftTail=temp;
                }else{
                    leftTail.next=temp;
                    leftTail=leftTail.next;
                }
            }else{
                if(rightHead==null){
                    rightHead=temp;
                    rightTail=temp;
                }else{
                    rightTail.next=temp;
                    rightTail=rightTail.next;
                }
            }

            temp=temp.next;
        }

        if(leftHead==null){
            return rightHead;
        }else{
            leftTail.next=rightHead;
            if(rightTail!=null){
                rightTail.next=null;
            }
            return leftHead;
        }


    }
}
